package demo6;

import java.util.Stack;

public class ExpressionEvaluator {

    // 定义运算符优先级
    private static int precedence(char op) {
        switch (op) {
            case '+':
            case '-':
                return 1;
            case '*':
            case '/':
                return 2;
        }
        return -1;
    }

    // 判断是否是运算符
    public static boolean isOperator(char ch) {
        return ch == '+' || ch == '-' || ch == '*' || ch == '/';
    }

    public static boolean isDigit(char ch) {
        return ch >= '0' && ch <= '9';  // 判断字符是否在 '0' 到 '9' 的范围内
    }

    // 打印栈的状态
    private static void printStacks(Stack<Character> operatorStack, StringBuilder outputQueue) {
        System.out.println("运算符栈: " + operatorStack);
        System.out.println("输出队列: " + outputQueue.toString().trim());
        System.out.println(); // 打印空行以分隔不同步骤的输出
    }

    // 中缀表达式转后缀表达式
    public static String infixToPostfix(String expression) {
        Stack<Character> operatorStack = new Stack<>();  // 操作符栈
        StringBuilder outputQueue = new StringBuilder(); // 记录结果
        char[] tokens = expression.toCharArray();

        for (int i = 0; i < tokens.length; i++) {
            char token = tokens[i];

            // 跳过空格
            if (token == ' ') continue;

            // 如果是数字或小数点，读取完整数字
            if (isDigit(token) || token == '.') {
                StringBuilder num = new StringBuilder();

                while (i < tokens.length && (Character.isDigit(tokens[i]) || tokens[i] == '.')) {
                    num.append(tokens[i]);
                    i++;
                }
                i--;  // 回退一位
                outputQueue.append(num).append(' ');  // 拼接作用     将完整的数字加入输出
                printStacks(operatorStack, outputQueue);  // 打印栈状态
            }
            // 如果是左括号，压入栈
            else if (token == '(') {
                operatorStack.push(token);
                printStacks(operatorStack, outputQueue);  // 打印栈状态
            }
            // 如果是右括号，弹出栈中的操作符直到遇到左括号
            else if (token == ')') {
                while (!operatorStack.isEmpty() && operatorStack.peek() != '(') {
                    outputQueue.append(operatorStack.pop()).append(' ');
                    printStacks(operatorStack, outputQueue);  // 打印栈状态
                }
                operatorStack.pop(); // 弹出左括号
                printStacks(operatorStack, outputQueue);  // 打印栈状态
            }
            // 如果是操作符
            else if (isOperator(token)) {
                while (!operatorStack.isEmpty() && precedence(operatorStack.peek()) >= precedence(token)) {
                    outputQueue.append(operatorStack.pop()).append(' ');
                    printStacks(operatorStack, outputQueue);  // 打印栈状态
                }
                operatorStack.push(token);
                printStacks(operatorStack, outputQueue);  // 打印栈状态
            }
        }

        // 将剩余的操作符依次弹出
        while (!operatorStack.isEmpty()) {
            outputQueue.append(operatorStack.pop()).append(' ');
            printStacks(operatorStack, outputQueue);  // 打印栈状态
        }

        return outputQueue.toString().trim();  // 去除尾部空格
    }

    public static void main(String[] args) {
        String expression = "( ( 3 + 2 ) * 4 ) - 5";
        System.out.println("后缀表达式: " + infixToPostfix(expression));
    }
}